/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //单调队列, 递减, 塞入元素大于末尾元素, 一直弹出
        std::deque<int> decreasingQue;
        int l = 0, r = 0;
        std::vector<int> results;
        for(; r < nums.size(); r++) {
            while (!decreasingQue.empty() && nums[r] > decreasingQue.back())
                decreasingQue.pop_back();

            decreasingQue.push_back(nums[r]);

            if (r - l + 1 == k) {
                results.push_back(decreasingQue.front());

                if (nums[l] == decreasingQue.front())
                    decreasingQue.pop_front();
                    
                l++;
            }
        }

        return results;
    }
};
// @lc code=end

